1. Field of the Invention
This invention relates to data movement among concurrent computers ("nodes"), and more particularly to a message passing network which links k-ary n-cube nodes (numbered 0, 1, . . . , N-1) together in a k-ary n-dimensional cube in which N=k.sup.n or n=log.sub.k N. Communication channels between nodes terminate in channel switching units located at each node in advance of the node's storage, memory and message processing circuitry.
The field of this invention relates more specifically to a new and improved self-timed channel routing, switching, and deadlock avoidance system in k-ary n-cube multiprocessor networks.
2. Brief Description of the Prior Art
Concurrent computing systems connected in a binary (2-ary) n-cube configuration are disclosed and claimed in applications assigned to the assignee of this application. For example, a concurrent computing system in which individual computers, each with a computational processor and a message-handling processor, are connected as a hypercube is described and claimed in an application entitled "Concurrent Computing System Through Asynchronous Communication Channels," filed on July 12, 1985 as Ser. No. 754,828 and assigned to California Institute of Technology. The identified application is referred to herein as the Seitz et al, Cosmic Cube application. As there described, N nodes (numbered 0, 1, ---- N-1) are connected together with a binary (or Boolean) n-dimensional cube in which N=2.sup.n or n=log.sub.2 N. The nodes are computers comprised of processors and memory, and the nodes communicate with each other by bidirectional communication links only along the edges of the cube. Representative examples of microprocessor hardware and software suitable for performing some of the data transfer features relevant to this invention are fully disclosed in the above-identified application. Specific portions of the Seitz et al Cosmic Cube application are referenced in detail hereinafter.
In an application entitled "Method and Apparatus for Implementing a Maximum-Likelihood Decoder in a Hypercube Network" filed on Sept. 27, 1985 having Ser. No. 781,224 by Fabrizio Pollara-Bozzola, now U.S. Pat. No. 4,730,322 issued Mar. 8, 1988, convolutional codes are decoded by the accumulated metric and survivor steps of the well-known Viterbi algorithm. The improved system divides the decoding operation in parallel among all processors which are assigned unique states of the trellis to compute at different stages on the trellis. In this and the Seitz et al Cosmic Cube application, X, Y, and Z indicate directions of communication in the cube. Each node is assigned a different binary coded identification label, which labels are uniquely ordered in the network. A destination descriptor accompanies each block of data and that destination descriptor is modulo-two added to the local label of a receiving node in order to control message routing.
Similar message routing is employed in another application entitled "Concurrent Hypercube Computing System with Improved Message Passing" filed on Apr. 1, 1986 as Ser. No. 846,721 naming J. C. Peterson et al as inventors. In the latter application separate control channels in addition to bidirectional communication channels link each adjacent node together.
As each of the above-identified applications suggest, the communication time and the amount of communication and control channel wiring involved, are significant factors in the application of concurrent computing to cube-connected systems. Deadlock-free routing is achieved in all of these applications by routing along successive dimensions. Such routing is accomplished by the store and forward approach as therein described.